package com.company.other.backtrack;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.stream.Collectors;

/**
 *
 * 给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
 * 你可以按 任何顺序 返回答案。
 * 示例 1：
 *
 * 输入：n = 4, k = 2
 * 输出：
 * [
 *   [2,4],
 *   [3,4],
 *   [2,3],
 *   [1,2],
 *   [1,3],
 *   [1,4],
 * ]
 * 提示：
 *
 * 1 <= n <= 20
 * 1 <= k <= n
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/combinations
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * */
public class Combine {
    public static void main(String[] args) {
        Combine combine = new Combine();
        List<List<Integer>> lists = combine.combine(20, 10);
        System.out.println("总共："+lists.size() +"种结果");
    }
    /**
     * 我是先做了剑指 Offer 38. 字符串的排列，来做的这道题
     * 方法：《剑指 Offer 38. 字符串的排列》一题类似，采用了回溯法
     * 优化思路：与求排列不相同的是，组合的研究对象少了顺序这一维度。如 [1,2,3] 、[1,3,2]、[2,3,1]这些组合都是一样的。所以按照简单的回溯，获取元素，必定会产生重复的组合。
     * 1. 一种解决方法：收集到所有的排列情况，然后对结果进行检查去重，因为排列的个数往往是一个很大的数字，代价是很大的
     * 2. 另一种办法也就是剪枝，需要预先对所有元素排序，但是可喜的是一般这一类题目，所给定的元素长度都不会很大，所以排序的成本自然就小了。总体而言，这种办法效率更高，况且这道题中的元素本来就是有顺序的。
     * 所以，为了使得得到的每个结果都不是重复的，可以先将所有元素通过大小关系进行排序，如[1,2,3] 或者 [3,2,1] ，然后在每次回溯生成list的时候，
     * - 如果使用的是增序排序，判断list中的最后一个元素是否是小于新的未被访问元素；
     * - 如果使用的是降序排序，判断list中的最后一个元素是否是大于新的未被访问元素；
     * 这样在收集到一个完成的list时，这个list就满足是唯一的组合
     * */
    public List<List<Integer>> combine(int n, int k){
        boolean[] visited = new boolean[n+1];
        List<List<Integer>> result = new ArrayList<>();
        backTrack(visited,k,new ArrayList<Integer>(),0,result);
        return result;
    }

    private void backTrack(boolean visited[],int k,List<Integer> list,int detailNum,List<List<Integer>> result) {
        //收集结果
        if(list.size() == k){
            List<Integer> newList = list.stream().collect(Collectors.toList());
            result.add(newList);
            return;
        }
        //递归回溯
        for (int i = detailNum + 1; i < visited.length; i++) {
            if(!visited[i]){
                list.add(i);
                visited[i] =true;
                backTrack(visited,k,list,i,result);
                list.remove(list.size() -1);
                visited[i]=false;
            }
        }
    }
}
